{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align=\"center\"> Prime Numbers using Python </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is a prime number?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Has to be a natural number (postive integer) \n",
    "2. Divisible by exactly 2 natural numbers.\n",
    "3. 1 is not a prime number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Task: Write a program to make a list of all prime numbers less than or equal to 20. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 1: For Loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize a list\n",
    "primes = []\n",
    "for possiblePrime in range(2, 21):\n",
    "    \n",
    "    # Assume number is prime until shown it is not. \n",
    "    isPrime = True\n",
    "    for num in range(2, possiblePrime):\n",
    "        if possiblePrime % num == 0:\n",
    "            isPrime = False\n",
    "      \n",
    "    if isPrime:\n",
    "        primes.append(possiblePrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 2: For Loop with Break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only difference is a break statement. Basically once you know that a number isn't prime why should you keep on testing it in the inner loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Initialize a list\n",
    "primes = []\n",
    "for possiblePrime in range(2, 21):\n",
    "    \n",
    "    # Assume number is prime until shown it is not. \n",
    "    isPrime = True\n",
    "    for num in range(2, possiblePrime):\n",
    "        if possiblePrime % num == 0:\n",
    "            isPrime = False\n",
    "            break\n",
    "      \n",
    "    if isPrime:\n",
    "        primes.append(possiblePrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 1 vs 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Approach 2 is more efficient. Say you were trying to check whether 15 is a prime number. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.DataFrame({'num': [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14],\n",
    "                   'isPrime Value After Iteration': [True, False, False, False, False, False, False, False, False, False, False, False, False],\n",
    "                   'Approach 1 Continue to Iterate?': (['yes'] * 13),\n",
    "                   'Approach 2 Continue to Iterate?': ['yes', 'no' ,'no' ,'no', 'no', 'no', 'no', 'no', 'no', 'no', 'no', 'no', 'no']}\n",
    "                   )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>num</th>\n",
       "      <th>isPrime Value After Iteration</th>\n",
       "      <th>Approach 1 Continue to Iterate?</th>\n",
       "      <th>Approach 2 Continue to Iterate?</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>2</td>\n",
       "      <td>True</td>\n",
       "      <td>yes</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>3</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>5</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>6</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>7</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>8</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>9</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>10</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>11</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>12</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>13</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>14</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    num  isPrime Value After Iteration Approach 1 Continue to Iterate?  \\\n",
       "0     2                           True                             yes   \n",
       "1     3                          False                             yes   \n",
       "2     4                          False                             yes   \n",
       "3     5                          False                             yes   \n",
       "4     6                          False                             yes   \n",
       "5     7                          False                             yes   \n",
       "6     8                          False                             yes   \n",
       "7     9                          False                             yes   \n",
       "8    10                          False                             yes   \n",
       "9    11                          False                             yes   \n",
       "10   12                          False                             yes   \n",
       "11   13                          False                             yes   \n",
       "12   14                          False                             yes   \n",
       "\n",
       "   Approach 2 Continue to Iterate?  \n",
       "0                              yes  \n",
       "1                               no  \n",
       "2                               no  \n",
       "3                               no  \n",
       "4                               no  \n",
       "5                               no  \n",
       "6                               no  \n",
       "7                               no  \n",
       "8                               no  \n",
       "9                               no  \n",
       "10                              no  \n",
       "11                              no  \n",
       "12                              no  "
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df[['num', 'isPrime Value After Iteration', 'Approach 1 Continue to Iterate?', 'Approach 2 Continue to Iterate?']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "\n",
    "possiblePrime = 15\n",
    "\n",
    "# Assume number is prime until shown it is not. \n",
    "isPrime = True\n",
    "for num in range(2, possiblePrime):\n",
    "    print(num)\n",
    "    if possiblePrime % num == 0:\n",
    "        isPrime = False\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n",
      "11\n",
      "12\n",
      "13\n",
      "14\n"
     ]
    }
   ],
   "source": [
    "\n",
    "possiblePrime = 15\n",
    "\n",
    "# Assume number is prime until shown it is not. \n",
    "isPrime = True\n",
    "for num in range(2, possiblePrime):\n",
    "    print(num)\n",
    "    if possiblePrime % num == 0:\n",
    "        isPrime = False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 3: For Loop, Break, and Square Root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When you are testing whether a nuber is prime, all you are doing is testing whether a number times another number is prime. Eventually you will get to a situation where you will multiply the same prime numbers against each other. \n",
    "\n",
    "Commutative property: When two numbers are multiplied together, the product is the same regardless of the order of the multiplicands. For example 4 * 2 = 2 * 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6 x8 is the same as 8 x 6 (can make a visual on this). The image above is all the factors for 48 (notice it gets repetitive). up a hill and down. communtative property of multiplication). Tipping point happens at the square root of a number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Initialize a list\n",
    "primes = []\n",
    "for possiblePrime in range(2, 21):\n",
    "    \n",
    "    # Assume number is prime until shown it is not. \n",
    "    isPrime = True\n",
    "    for num in range(2, int(possiblePrime ** 0.5) + 1):\n",
    "        if possiblePrime % num == 0:\n",
    "            isPrime = False\n",
    "            break\n",
    "      \n",
    "    if isPrime:\n",
    "        primes.append(possiblePrime)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 17, 19]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "primes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach 4: Sieve of Eratosthenes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "I will add in the future if necessary. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
